k-d tree

Close variations:

implicit k-d tree, a k-d tree defined by an implicit splitting function rather than an explicitly-stored set of splits

min/max k-d tree, a k-d tree that associates a minimum and maximum value with each of its nodes

Relaxed k-d tree, a k-d tree such that the discriminants in each node are arbitrary

Related variations:

Quadtree, a space-partitioning structure that splits in two dimensions simultaneously, so that each node has 4 children

Octree, a space-partitioning structure that splits in three dimensions simultaneously, so that each node has 8 children

Ball tree, a multi-dimensional space partitioning useful for nearest neighbor search

R-tree and bounding interval hierarchy, structure for partitioning objects rather than points, with overlapping regions

Vantage-point tree, a variant of a k-d tree that uses hyperspheres instead of hyperplanes to partition the data

Problems that can be addressed with k-d trees:

Recursive partitioning, a technique for constructing statistical decision trees that are similar to k-d trees

Klee's measure problem, a problem of computing the area of a union of rectangles, solvable using k-d trees

Guillotine problem, a problem of finding a k-d tree whose cells are large enough to contain a given set of rectangles